package main.leetcode.offer.secondround.from03to50;

import java.util.ArrayList;

/** 59-I.滑动窗口的最大值 */
public class ex59I {
    public static void main(String[] args) {
        System.out.println(new ex59I().maxInWindows(new int[] {2, 3, 4, 2, 6, 2, 5, 1}, 3));
    }

    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        int n = num.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; ++i) {
            if (i % size == 0) {
                left[i] = num[i];
            } else {
                left[i] = Math.max(left[i - 1], num[i]);
            }
        }

        for (int i = n - (n % size) - 1; i >= 0; --i) {
            if ((i + 1) % size == 0) {
                right[i] = num[i];
            } else {
                right[i] = Math.max(right[i + 1], num[i]);
            }
        }

        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < n - 1; ++i) {
            res.add(Math.max(left[i + size - 1], right[i]));
        }
        return res;
    }
}
